/*
 * INSANE - Interactive Structural Analysis Environment
 *
 * Copyright (C) 2003-2005
 * Universidade Federal de Minas Gerais
 * Escola de Engenharia
 * Departamento de Engenharia de Estruturas
 * 
 * Author's email :    insane@dees.ufmg.br
 * Author's website :  http://www.dees.ufmg.br/insane
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

package br.ufmg.dees.insane.model.geo.computationalGeometry;

import java.awt.geom.Point2D;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Vector;

/**
 * @author Penna,S.S. & Pitangueira, Roque
 * @since 19/10/2006
 * 
 * ConvexHull.java
 * 
 * Adapted from Sedgewick, Algorithms
 *                   And
 * FreeMind - A Program for creating and viewing Mindmaps
 * Copyright (C) 2000-2001  Joerg Mueller <joergmueller@bigfoot.com>
 * See COPYING for Details
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 * 
 */
public final class ConvexHull{
	
	public ConvexHull(){
		
	}
	    
	private int ccw(Point2D.Double p0, Point2D.Double p1, Point2D.Double p2) {
		double dx1, dx2, dy1,dy2;
        dx1 = p1.x - p0.x;         dy1 = p1.y - p0.y;  
        dx2 = p2.x - p0.x;         dy2 = p2.y - p0.y;
        double comp = dx1 * dy2 - dy1 * dx2;
        if( comp > 0 ) 
            return 1;
        if ( comp < 0 ) 
            return -1;
        if((dx1 * dx2 < 0) || (dy1*dy2 < 0))
            return -1;
        if(dx1*dx1 + dy1*dy1 >= dx2*dx2 + dy2*dy2)
            return 0;
        return 1;
	}
	    
	private class thetaComparator implements Comparator<Object>{
		Point2D.Double p0;
        
		private thetaComparator(Point2D.Double p0) {
            this.p0 = new Point2D.Double(p0.x,p0.y);
        }

        /* the < relation.*/
        public int compare(Object p1, Object p2) {
            double comp = theta (p0,(Point2D.Double)p1) - theta (p0,(Point2D.Double)p2);
            if(((Point2D.Double)p1).equals(p2))
                return 0;
            if(comp > 0) 
                return 1;
            if(comp < 0)
                return -1;
            // here, the points are collinear with p0 (i.e. p0,p1,p2 are on one line). So we reverse the compare relation to get that nearer points are greater.
            // we take the point that is nearer to p0:
            double dx1, dx2, dy1,dy2;
            dx1 = ((Point2D.Double) p1).x - ((Point2D.Double) p0).x;         dy1 = ((Point2D.Double) p1).y - ((Point2D.Double) p0).y;  
            dx2 = ((Point2D.Double) p2).x - ((Point2D.Double) p0).x;         dy2 = ((Point2D.Double) p2).y - ((Point2D.Double) p0).y;
            double comp2 = (dx1 * dx1 + dy1 * dy1) - (dx2 * dx2 + dy2 * dy2);
            if (comp2 > 0) 
                return -1;
            if (comp2 < 0) 
                return 1;
            return 0;
        }
        
        private double theta(Point2D.Double p1, Point2D.Double p2) {
            double dx, dy, ax, ay;
            double t;
            dx = p2.x - p1.x; ax = Math.abs(dx);
            dy = p2.y - p1.y; ay = Math.abs(dy);
            if((dx == 0) && (dy==0))
                t = 0;
            else
                t = ((double) dy) / ((double) (ax+ay));
            if(dx < 0) 
                t = 2f - t;
            else {
                if(dy < 0)
                    t = 4f+t;
            }
            return t * 90f;
        }	
	}
	
	private Vector doGraham(Vector<Object> p){
		int i,min,M;
        Point2D.Double t;
        min = 0;
        // search for minimum:
        for(i=1; i < p.size(); ++i) {
            if( ((Point2D.Double) p.get(i)).y < ((Point2D.Double) p.get(min)).y )
                min = i;
        }
        // continue along the values with same y component
        for(i=0; i < p.size(); ++i) {
            if(( ((Point2D.Double) p.get(i)).y == ((Point2D.Double) p.get(min)).y ) && ( ((Point2D.Double) p.get(i)).x > ((Point2D.Double) p.get(min)).x ))
                {  min = i; }
        }
        // swap:
        t = (Point2D.Double) p.get(0);
        p.set(0, p.get(min));
        p.set(min,  t);
        thetaComparator comp = new thetaComparator((Point2D.Double) p.get(0));
        Collections.sort(p, comp);
        p.add(0,  new Point2D.Double(((Point2D.Double) p.get(p.size()-1)).x,((Point2D.Double) p.get(p.size()-1)).y)); // the first is the last.
        M = 3;
        for(i=4; i < p.size(); ++i) {
        	while(ccw((Point2D.Double)p.get(M), (Point2D.Double)p.get(M-1), (Point2D.Double)p.get(i)) >= 0) {
        		M--;
        	}
        	M++;
        	// swap:
        	t = (Point2D.Double) p.get(M);         p.set(M, p.get(i));         p.set(i,  t);
        }
        p.remove(0);
        p.setSize(M);
        return p;
	}
	    
	public Vector calculateHull(LinkedList coordinates) {
		Vector<Object> q = new Vector<Object>();
        ListIterator coordinates_it = coordinates.listIterator();
        while(coordinates_it.hasNext()) {
            q.add( coordinates_it.next());
        }
        Vector res = doGraham(q);
        return res;
	}


	    
	public static void main(String[] args){
//			Vertex v1 = new Vertex("1", new IPoint3d(1,1));
//			Vertex v2 = new Vertex("2", new IPoint3d(7,3));
//			Vertex v3 = new Vertex("3", new IPoint3d(4,4));
//			Vertex v4 = new Vertex("4", new IPoint3d(3.5,1));
//			Vertex v5 = new Vertex("5", new IPoint3d(4,5));
//			Vertex v6 = new Vertex("6", new IPoint3d(10,10));
//			Vertex v7 = new Vertex("7", new IPoint3d(10,10));
	 
			Point2D p1 = new Point2D.Double(1.0,1.0);
			Point2D p2 = new Point2D.Double(2.0,1.0);
			Point2D p3 = new Point2D.Double(2.0,2.0);
			Point2D p4 = new Point2D.Double(1.0,2.0);
			Point2D p5 = new Point2D.Double(1.5,1.5);
			Point2D p6 = new Point2D.Double(0.5,1.5);
			Point2D p7 = new Point2D.Double(1.0,1.5);
			LinkedList<Point2D> list = new LinkedList<Point2D>();
			list.add(p1);
			list.add(p2);
			list.add(p3);
			list.add(p4);
			list.add(p5);
			list.add(p6);
			list.add(p7);
			
			ConvexHull comv = new ConvexHull();
			 
			Vector auxList = comv.calculateHull(list);
			 
			for(int i =0;i<auxList.size();i++){
				System.out.println("Vertice "+(auxList.get(i)));
			}
	   
	}
	    
	
//*********************************************************************************************	
}//end of this class